Image matching processing that determines coincidences among a plurality of images is typically performed by comparing feature quantities that are extracted from the images. For example, an image search system matches each of a plurality of images against an input image by comparing the feature quantities of the plurality of images stored in a database and a feature quantity obtained from the input image. In general, a feature quantity is represented by multidimensional vector data that is referred to as a feature vector.
FIG. 19 is a diagram illustrating an example of calculating a distance between pieces of vector data in typical matching processing.
Comparison of vector data is typically performed by calculating differences for respective elements between two pieces of vector data of comparison targets and comparing the aggregated value of the differences with a threshold. In this description, the aggregated difference is referred to as a distance, and a calculation of the distance between two pieces of vector data is referred to as a distance calculation. For example, when each element of vector data is represented by a single value, the sum of absolute values of differences of the values for respective elements is used as a distance. In other words, when two pieces of vector data are a and b, a distance between the vector data a and b is calculated by Σ|a[j]−b[j]| as illustrated in FIG. 19. Here, a[j] and b[j] respectively indicate j-th elements of pieces of the vector data a and b, and Σ indicates accumulation with respect to all the elements. In comparing of the calculated distance, for example, when the distance is equal to or less than a predetermined comparison threshold, the two pieces of vector data are determined as coinciding with each other. On the other hand, when the distance is larger than the predetermined comparison threshold, the two pieces of vector data may be determined as not coinciding with each other.
In the matching processing of an image search system, a distance is calculated between each piece of vector data in a database and vector data of a search target.
FIG. 20 is an example of a typical matching processing program. In the example of FIG. 20, the number of pieces of vector data in a database is 12 and the number of elements in each piece of the vector data is 8. Here, u[i][j] is a j-th element of an i-th piece of vector data in the database, v[j] is a j-th element of vector data of a search target. T is a comparison threshold and, when a distance d is smaller than T, the i-th piece of vector data in the database and the vector data of the search target are determined as coinciding with each other (line numbers 8 and 9).
When a large amount of vector data is included in a database, lengthy search time becomes a problem. To reduce search time, it is essential to accelerate a distance calculation between pieces of vector data.
The method of accelerating a distance calculation between pieces of vector data includes, for example, truncation determination. FIG. 21 is a diagram illustrating an application example of the truncation determination in typical matching processing. In the truncation determination, a distance obtained by accumulating only differences of some elements of vector data in the middle of accumulation, is compared with a predetermined truncation threshold. Then, when the distance in the middle of accumulation is equal to or more than the truncation threshold (when satisfying the truncation condition), a further distance calculation is determined as unnecessary and the distance calculation ends as illustrated in FIG. 21 (truncation processing).
FIG. 22 is an example of a program that adapts truncation determination in typical matching processing. In the example of FIG. 22, when a distance in the middle of accumulation is equal to or more than a truncation threshold T, truncation processing is performed (line numbers 7 and 8). In this case, the comparison threshold T is used as a truncation threshold.
FIG. 23 is a diagram illustrating an example of elements, for which difference calculations are performed, when truncation determination is adapted in typical matching processing. In the example of FIG. 23, the elements indicated by shades represent elements, for which difference calculations are not performed (difference calculations are not required), and the other portion represents elements, for which difference calculations are performed (difference calculations are necessary) among vector data u[0] . . . u[11] in a database. In this case, difference calculations are performed for all dimensions with respect to vector data u[2], while a difference calculation is performed only for the first dimension with respect to other vector data. In other words, difference calculations are performed 19 times for 19 elements.
For example, PTL 1 discloses an example of a system where such truncation determination is performed for calculating a distance between pieces of vector data in image matching.